The present invention relates to packet-switched data communication networks and particularly to a network switch which includes a facility for demultiplexing data received in the form of packets over a high speed serial link to a multiplicity of channels or ports which are intended or constructed to operate at an individually lower frequency than the high speed link.
It is known, in respect of a multi-port network switch which is adapted or intended for operation at a particular data rate, or possibly a plurality of data rates such as ten and one hundred megabits per second, to dedicate a multiplicity of ports for the reception of data at a much higher data rate, such as one gigabit per second, and to direct packets to the dedicated multiplicity of ports by means of a demultiplexer which is controlled by a comparatively short address word obtained by hashing a longer address or combination of addresses in each data packet. The operation of hashing, whatever particular hashing function is used, reduces the comparatively wide address data to a comparatively short address, such as a two-bit word if the demultiplexer is to control only four channels or ports, and it is characteristic of hashing functions that the same input address data (or combination of addresses) will always map to the same short hashed address.
Controlling a demultiplexer in this manner is more appropriate than, for example, allotting successive packets to the different ports in a round robin manner, because the latter does not guarantee that packets having the same address or source address and destination address combination will be handled in the same chronological order as they have been transmitted over the high speed link. In particular, it is common for ports to contain respective FIFO stores or other means of temporarily holding received data packets in respective queues
The onward forwarding of data packets in those queues depends on, for example, available bandwidth in devices connected to the respective ports of the switch, the outcome of contention resolution between high and low priority packets and so forth. It is desirable to ensure that packets having corresponding address data, and more particularly having the same source address and destination address combination, are directed to the same receive queue in the same order in which they have been received.
The disadvantage of known schemes for controlling demultiplexing by hashing address data on incoming packets is that non-uniform distribution of traffic may result in a more strongly non-uniform allocation of packets to particular ports, which might initiate flow control or bandwidth limitation measures but is in any event undesirable in a scheme which is intended to distribute data from a high speed link to a multiplicity of lower speed links; the combined throughput of the lower speed links will normally always be a maximum if the links or ports carry equal shares of the incoming traffic.
The basis of the present invention is a combination of various features. There must be available a multiplicity of hash functions, which may be stored in memory or represent different configurations of a logic array. These hash functions may be selectively applied to demultiplex incoming packets so that packets having the same relevant address data (as explained below) are for a given hash function directed to the same queue in correct chronological order. Further, there is a monitoring means which applies to the packets received by the group of ports, or at least to the selected address data, a multiplicity of hash functions so as to obtain a statistical analysis of the effect of applying a variety of hash functions to the selected address data of the incoming packet traffic. The monitoring process is performed while the actual demultiplexing of the incoming traffic continues in accordance with a selected or default hash function, The scheme enables the selection of a hash function by a statistical analysis of the data obtained by the monitoring process and therefore the selection of that hash function which having regard to the flow of traffic will most nearly equalize the distribution of packets to the multiplicity of dedicated ports.
Further features of the invention will be apparent from the following description with reference to the drawings.